using BepuUtilities;
using BepuUtilities.Collections;
using BepuUtilities.Memory;
using System;
using System.Diagnostics;
using System.Runtime.CompilerServices;
using System.Runtime.InteropServices;
#if MYCODE
using BepuUtilities.Vectors;
#else
using System.Numerics;
#endif

namespace BepuPhysics.Collidables
{
    /// <summary>
    /// 存储对组成凸面之一的点的引用。
    /// </summary>
    public struct HullFace
    {
        public Buffer<int> OriginalVertexMapping;
        public Buffer<int> VertexIndices;

        /// <summary>
        /// 获取面中的顶点数。
        /// </summary>
        public int VertexCount
        {
            [MethodImpl(MethodImplOptions.AggressiveInlining)]
            get { return VertexIndices.Length; }
        }

        /// <summary>
        /// 获取与源点集中给定面顶点索引关联的顶点的索引。
        /// </summary>
        /// <param name="index">面的顶点列表的索引。</param>
        /// <return>与源点集中给定面顶点索引关联的顶点的索引。</return>
        public int this[int index]
        {
            [MethodImpl(MethodImplOptions.AggressiveInlining)]
            get { return OriginalVertexMapping[VertexIndices[index]]; }
        }
    }

    /// <summary>
    /// 表示凸包的原始数据。
    /// </summary>
    /// <remarks>This is not yet transformed into a runtime format. It requires additional processing to be used in a ConvexHull shape; see ConvexHullHelper.ProcessHull.</remarks>
    public struct HullData
    {
        /// <summary>
        /// 将凸包上的点映射回原始点集。
        /// </summary>
        public Buffer<int> OriginalVertexMapping;
        /// <summary>
        /// 组成外壳面的索引列表。由FaceIndices索引的各个面。
        /// </summary>
        public Buffer<int> FaceVertexIndices;
        /// <summary>
        /// 每个面的FaceVertexIndices中的起始索引。
        /// </summary>
        public Buffer<int> FaceStartIndices;

        [MethodImpl(MethodImplOptions.AggressiveInlining)]
        public void GetFace(int faceIndex, out HullFace face)
        {
            var nextFaceIndex = faceIndex + 1;
            var start = FaceStartIndices[faceIndex];
            var end = nextFaceIndex == FaceStartIndices.Length ? FaceVertexIndices.Length : FaceStartIndices[nextFaceIndex];
            FaceVertexIndices.Slice(start, end - start, out face.VertexIndices);
            face.OriginalVertexMapping = OriginalVertexMapping;
        }

        public void Dispose(BufferPool pool)
        {
            pool.Return(ref OriginalVertexMapping);
            pool.Return(ref FaceVertexIndices);
            pool.Return(ref FaceStartIndices);
        }
    }

    /// <summary>
    /// 从点云创建和处理凸面外壳的辅助方法。
    /// </summary>
    public static class ConvexHullHelper
    {
        static void FindExtremeFace(in Vector3Wide basisX, in Vector3Wide basisY, in Vector3Wide basisOrigin, in EdgeEndpoints sourceEdgeEndpoints, ref Buffer<Vector3Wide> pointBundles, in Vector<int> indexOffsets, int pointCount,
            ref Buffer<Vector<float>> projectedOnX, ref Buffer<Vector<float>> projectedOnY, in Vector<float> planeEpsilon, ref QuickList<int> vertexIndices, out Vector3 faceNormal)
        {
            Debug.Assert(projectedOnX.Length >= pointBundles.Length && projectedOnY.Length >= pointBundles.Length && vertexIndices.Count == 0 && vertexIndices.Span.Length >= pointBundles.Length * Vector<float>.Count);
            // 找到基于候选对象的原点,该原点在投影到由basisX和basisY跨越的平面时具有最小的basisY角度。
            // 角度=acos(y/||(x,y)||)
            // 余角=y/||(x,y)||
            // 余角^2=y^2/||(x,y)||^2
            // 然后,我们可以使用以下命令比较样本0和1：
            // Sign(Y0)*y0^2*||(x1,y1)||^2>sign(Y1)*y1^2*||(x0,y0)||^2
            // 没有除法、平方根或三角法。
            Vector3Wide.Subtract(pointBundles[0], basisOrigin, out var toCandidate);
            ref var x = ref projectedOnX[0];
            ref var y = ref projectedOnY[0];
            Vector3Wide.Dot(basisX, toCandidate, out x);
            // 如果x为负数,则意味着某个数值问题已导致某个点超出了生成此面请求的边界平面。
            // 我们会把它当作在飞机上一样对待。
            x = Vector.Max(Vector<float>.Zero, x);
            Vector3Wide.Dot(basisY, toCandidate, out y);
            var bestNumerators = y * y;
            var bestDenominators = bestNumerators + x * x;
            bestNumerators = Vector.ConditionalSelect(Vector.LessThan(y, Vector<float>.Zero), -bestNumerators, bestNumerators);
            // 忽略源边缘。
            var edgeIndexA = new Vector<int>(sourceEdgeEndpoints.A);
            var edgeIndexB = new Vector<int>(sourceEdgeEndpoints.B);
            var pointCountBundle = new Vector<int>(pointCount);
            const float minimumDistanceSquaredScalar = 1e-14f;
            var minimumDistanceSquared = new Vector<float>(minimumDistanceSquaredScalar);
            var ignoreSlot = Vector.BitwiseOr(
                Vector.BitwiseOr(Vector.GreaterThanOrEqual(indexOffsets, pointCountBundle), Vector.LessThan(bestDenominators, minimumDistanceSquared)),
                Vector.BitwiseOr(Vector.Equals(indexOffsets, edgeIndexA), Vector.Equals(indexOffsets, edgeIndexB)));
            bestDenominators = Vector.ConditionalSelect(ignoreSlot, Vector<float>.One, bestDenominators);
            bestNumerators = Vector.ConditionalSelect(ignoreSlot, new Vector<float>(float.MinValue), bestNumerators);
            var bestIndices = indexOffsets;
            for (int i = 1; i < pointBundles.Length; ++i)
            {
                Vector3Wide.Subtract(pointBundles[i], basisOrigin, out toCandidate);
                x = ref projectedOnX[i];
                y = ref projectedOnY[i];
                Vector3Wide.Dot(basisX, toCandidate, out x);
                x = Vector.Max(Vector<float>.Zero, x); // 与前面相同-防止边界平面之外的数值错误查找点。
                Vector3Wide.Dot(basisY, toCandidate, out y);
                var candidateNumerator = y * y;
                var candidateDenominator = candidateNumerator + x * x;
                candidateNumerator = Vector.ConditionalSelect(Vector.LessThan(y, Vector<float>.Zero), -candidateNumerator, candidateNumerator);

                var candidateIndices = indexOffsets + new Vector<int>(i << BundleIndexing.VectorShift);
                ignoreSlot = Vector.BitwiseOr(
                    Vector.BitwiseOr(Vector.GreaterThanOrEqual(candidateIndices, pointCountBundle), Vector.LessThan(candidateDenominator, minimumDistanceSquared)),
                    Vector.BitwiseOr(Vector.Equals(candidateIndices, edgeIndexA), Vector.Equals(candidateIndices, edgeIndexB)));
                var useCandidate = Vector.AndNot(Vector.GreaterThan(candidateNumerator * bestDenominators, bestNumerators * candidateDenominator), ignoreSlot);
                bestIndices = Vector.ConditionalSelect(useCandidate, candidateIndices, bestIndices);
                bestNumerators = Vector.ConditionalSelect(useCandidate, candidateNumerator, bestNumerators);
                bestDenominators = Vector.ConditionalSelect(useCandidate, candidateDenominator, bestDenominators);
            }
            var bestNumerator = bestNumerators[0];
            var bestDenominator = bestDenominators[0];
            var bestIndex = bestIndices[0];
            for (int i = 1; i < Vector<float>.Count; ++i)
            {
                var candidateNumerator = bestNumerators[i];
                var candidateDenominator = bestDenominators[i];
                if (candidateNumerator * bestDenominator > bestNumerator * candidateDenominator)
                {
                    bestNumerator = candidateNumerator;
                    bestDenominator = candidateDenominator;
                    bestIndex = bestIndices[i];
                }
            }
            // 我们现在有了最好的索引,但同一平面上可能有多个顶点。通过对结果进行第二次遍历,可以一次捕获所有这些结果。
            // 我们要检查的平面法线是(-BestY,Best X)/||(-Best,Best X)||。
            // (这不是非常快,但是相当简单。替代方案是在发现共面三角形时以递增方式组合它们
            // 或在创建共面三角形后使用查找共面三角形的后处理。)
            BundleIndexing.GetBundleIndices(bestIndex, out var bestBundleIndex, out int bestInnerIndex);
            var bestX = projectedOnX[bestBundleIndex][bestInnerIndex];
            var bestY = projectedOnY[bestBundleIndex][bestInnerIndex];
            // 旋转偏移以指向外部。
            var projectedPlaneNormalNarrow = Vector2.Normalize(new Vector2(-bestY, bestX));
            Vector2Wide.Broadcast(projectedPlaneNormalNarrow, out var projectedPlaneNormal);
            for (int i = 0; i < pointBundles.Length; ++i)
            {
                var dot = projectedOnX[i] * projectedPlaneNormal.X + projectedOnY[i] * projectedPlaneNormal.Y;
                var coplanar = Vector.LessThanOrEqual(Vector.Abs(dot), planeEpsilon);
                if (Vector.LessThanAny(coplanar, Vector<int>.Zero))
                {
                    var bundleBaseIndex = i << BundleIndexing.VectorShift;
                    var localIndexMaximum = pointCount - bundleBaseIndex;
                    if (localIndexMaximum > Vector<int>.Count)
                        localIndexMaximum = Vector<int>.Count;
                    for (int j = 0; j < localIndexMaximum; ++j)
                    {
                        if (coplanar[j] < 0)
                        {
                            vertexIndices.AllocateUnsafely() = bundleBaseIndex + j;
                        }
                    }
                }
            }
            Vector3Wide.ReadFirst(basisX, out var basisXNarrow);
            Vector3Wide.ReadFirst(basisY, out var basisYNarrow);
            faceNormal = basisXNarrow * projectedPlaneNormalNarrow.X + basisYNarrow * projectedPlaneNormalNarrow.Y;
        }


        static int FindNextIndexForFaceHull(in Vector2 start, in Vector2 previousEdgeDirection, ref QuickList<Vector2> facePoints)
        {
            // 使用AOS版本,因为在大多数情况下,给定面上的点数往往非常少。
            // 与3D版本的想法相同-找到离上一条边最近的下一条边。这里暂时不需要担心共线点。
            var bestIndex = -1;
            float bestNumerator = -float.MaxValue;
            float bestDenominator = 1;
            var startToCandidate = facePoints[0] - start;
            var candidateDenominator = startToCandidate.LengthSquared();
            var dot = Vector2.Dot(startToCandidate, previousEdgeDirection);
            var candidateNumerator = dot * dot;
            candidateNumerator = dot < 0 ? -candidateNumerator : candidateNumerator;
            if (candidateDenominator > 0)
            {
                bestNumerator = candidateNumerator;
                bestDenominator = candidateDenominator;
                bestIndex = 0;
            }
            for (int i = 1; i < facePoints.Count; ++i)
            {
                startToCandidate = facePoints[i] - start;
                dot = Vector2.Dot(startToCandidate, previousEdgeDirection);
                var absCandidateNumerator = dot * dot;
                candidateNumerator = dot < 0 ? -absCandidateNumerator : absCandidateNumerator;
                candidateDenominator = startToCandidate.LengthSquared();
                // 当心共线的点。如果角度相同,则拾取距离较远的点。
                var candidate = candidateNumerator * bestDenominator;
                var currentBest = bestNumerator * candidateDenominator;
                var epsilon = 1e-6 * absCandidateNumerator * bestDenominator;
                if (candidate > currentBest - epsilon)
                {
                    // 候选人和当前最佳角度可能非常相似。
                    // 只有在距离较远的情况下才使用候选人。
                    if (candidate < currentBest + epsilon && candidateDenominator <= bestDenominator)
                    {
                        continue;
                    }
                    bestNumerator = candidateNumerator;
                    bestDenominator = candidateDenominator;
                    bestIndex = i;
                }
            }
            // 请注意,如果所有点都位于起点之上,则可能返回-1。
            return bestIndex;
        }

        static void ReduceFace(ref QuickList<int> faceVertexIndices, in Vector3 faceNormal, ref Span<Vector3> points, ref QuickList<Vector2> facePoints, ref Buffer<bool> allowVertex, ref QuickList<int> reducedIndices)
        {
            Debug.Assert(facePoints.Count == 0 && reducedIndices.Count == 0 && facePoints.Span.Length >= faceVertexIndices.Count && reducedIndices.Span.Length >= faceVertexIndices.Count);
            for (int i = faceVertexIndices.Count - 1; i >= 0; --i)
            {
                if (!allowVertex[faceVertexIndices[i]])
                    faceVertexIndices.RemoveAt(i);
            }
            if (faceVertexIndices.Count <= 3)
            {
                // 太小了,不需要计算船体。直接复制。
                for (int i = 0; i < faceVertexIndices.Count; ++i)
                {
                    reducedIndices.AllocateUnsafely() = faceVertexIndices[i];
                }
                if (faceVertexIndices.Count == 3)
                {
                    // 完全减速是没有意义的,但我们确实需要检查三角形的缠绕情况。
                    ref var a = ref points[reducedIndices[0]];
                    ref var b = ref points[reducedIndices[1]];
                    ref var c = ref points[reducedIndices[2]];
                    // 逆时针方向应导致面法线指向外部。
                    var ab = b - a;
                    var ac = c - a;
                    var uncalibratedNormal = Vector3.Cross(ab, ac);
                    if (uncalibratedNormal.LengthSquared() < 1e-14f)
                    {
                        // 这张脸退化了。
                        if (ab.LengthSquared() > 1e-14f)
                        {
                            allowVertex[reducedIndices[2]] = false;
                            reducedIndices.FastRemoveAt(2);
                        }
                        else if (ac.LengthSquared() > 1e-14f)
                        {
                            allowVertex[reducedIndices[1]] = false;
                            reducedIndices.FastRemoveAt(1);
                        }
                        else
                        {
                            allowVertex[reducedIndices[1]] = false;
                            allowVertex[reducedIndices[2]] = false;
                            reducedIndices.Count = 1;
                        }
                    }
                    else
                    {
                        if (Vector3.Dot(faceNormal, uncalibratedNormal) < 0)
                            Helpers.Swap(ref reducedIndices[0], ref reducedIndices[1]);
                    }
                }
                return;
            }
            Helpers.BuildOrthnormalBasis(faceNormal, out var basisX, out var basisY);
            Vector2 centroid = default;
            for (int i = 0; i < faceVertexIndices.Count; ++i)
            {
                ref var source = ref points[faceVertexIndices[i]];
                ref var facePoint = ref facePoints.AllocateUnsafely();
                facePoint = new Vector2(Vector3.Dot(basisX, source), Vector3.Dot(basisY, source));
                centroid += facePoint;
            }
            centroid /= faceVertexIndices.Count;
            var greatestDistanceSquared = -1f;
            var initialIndex = 0;
            for (int i = 0; i < faceVertexIndices.Count; ++i)
            {
                ref var facePoint = ref facePoints[i];
                var distanceSquared = (facePoint - centroid).LengthSquared();
                if (greatestDistanceSquared < distanceSquared)
                {
                    greatestDistanceSquared = distanceSquared;
                    initialIndex = i;
                }
            }

            if (greatestDistanceSquared < 1e-14f)
            {
                // 这张脸退化了。
                for (int i = 0; i < faceVertexIndices.Count; ++i)
                {
                    allowVertex[faceVertexIndices[i]] = false;
                }
                return;
            }
            var greatestDistance = (float)Math.Sqrt(greatestDistanceSquared);
            var initialOffsetDirection = (facePoints[initialIndex] - centroid) / greatestDistance;
            var previousEdgeDirection = new Vector2(initialOffsetDirection.Y, -initialOffsetDirection.X);
            reducedIndices.AllocateUnsafely() = faceVertexIndices[initialIndex];

            var previousEndIndex = initialIndex;
            while (true)
            {
                // 如果面完全退化,则返回-1。
                var nextIndex = FindNextIndexForFaceHull(facePoints[previousEndIndex], previousEdgeDirection, ref facePoints);
                if (nextIndex == -1 || nextIndex == initialIndex)
                {
                    break;
                }
                reducedIndices.AllocateUnsafely() = faceVertexIndices[nextIndex];
                previousEdgeDirection = Vector2.Normalize(facePoints[nextIndex] - facePoints[previousEndIndex]);
                previousEndIndex = nextIndex;
            }

            // 忽略不在面外部边界上的任何顶点。
            for (int i = 0; i < faceVertexIndices.Count; ++i)
            {
                var index = faceVertexIndices[i];
                if (!reducedIndices.Contains(index))
                {
                    allowVertex[index] = false;
                }
            }
        }

        [StructLayout(LayoutKind.Explicit)]
        public struct EdgeEndpoints : IEqualityComparerRef<EdgeEndpoints>
        {
            [FieldOffset(0)]
            public int A;
            [FieldOffset(4)]
            public int B;

            [MethodImpl(MethodImplOptions.AggressiveInlining)]
            public bool Equals(ref EdgeEndpoints a, ref EdgeEndpoints b)
            {
                return Unsafe.As<int, long>(ref a.A) == Unsafe.As<int, long>(ref b.A) || (a.A == b.B && a.B == b.A);
            }

            [MethodImpl(MethodImplOptions.AggressiveInlining)]
            public int Hash(ref EdgeEndpoints item)
            {
                return item.A ^ item.B;
            }

            public override string ToString()
            {
                return $"({A}, {B})";
            }
        }
        struct EdgeToTest
        {
            public EdgeEndpoints Endpoints;
            public Vector3 FaceNormal;
            public int FaceIndex;
        }

        // 公共结构调试步骤
        // {
        // Public EdgeEndpoint SourceEdge;
        // 通讯组列表<int>Raw;
        // 公有列表<int>精简;
        // public bool[]AllowVertex;
        // 公共向量3脸部正常;
        // 公共向量3,BasisX;
        // 公众向量3基本Y;

        // 公共调试步骤(EdgeEndpoints sourceEdge,ref QuickList<int>raw,in Vector3 faceNormal,in Vector3 bassisX,in Vector3 bassisY)
        // {
        // SourceEdge=sourceEdge;
        // faceNormal=faceNormal;
        // BasisX=basisX;
        // BasisY=BasisY;
        // raw=新列表<int>();
        // for(int i=0;i<raw.Count;++i)
        // {
        // Raw.Add(RAW[i]);
        // }
        // Reduced=默认值;
        // AllowVertex=默认值;
        // }

        // public void AddReduced(引用快速列表<int>Reduced,引用缓冲区<bool>allowVertex)
        // {
        // Reduced=新建列表<int>();
        // for(int i=0;i<Reduced.Count;++i)
        // {
        // Reduced.Add(Reduced[i]);
        // }
        // AllowVertex=new bool[allowVertex.Length];
        // for(int i=0;i<allowVertex.Length;++i)
        // {
        // AllowVertex[i]=AllowVertex[i];
        // }
        // }


        // }

        /// <summary>
        /// 计算点集合的凸包。
        /// </summary>
        /// <param name="Points">用于计算的凸包的点集。</param>
        /// <param name="pool">创建外壳时从中拉取内存的缓冲池。</param>
        /// <param name="hullData">输入点集的凸包。</param>
        public static void ComputeHull(Span<Vector3> points, BufferPool pool, out HullData hullData)
        {
            if (points.Length <= 0)
            {
                hullData = default;
                // Steps=新建列表<DebugStep>();
                return;
            }
            if (points.Length <= 3)
            {
                // 如果输入太小,无法实际形成体积外壳线,只需直接输出输入即可。
                pool.Take(points.Length, out hullData.OriginalVertexMapping);
                for (int i = 0; i < points.Length; ++i)
                {
                    hullData.OriginalVertexMapping[i] = i;
                }
                if (points.Length == 3)
                {
                    pool.Take(1, out hullData.FaceStartIndices);
                    pool.Take(3, out hullData.FaceVertexIndices);
                    hullData.FaceStartIndices[0] = 0;
                    // 没有音量,所以缠绕不要紧。
                    hullData.FaceVertexIndices[0] = 0;
                    hullData.FaceVertexIndices[1] = 1;
                    hullData.FaceVertexIndices[2] = 2;
                }
                else
                {
                    hullData.FaceStartIndices = default;
                    hullData.FaceVertexIndices = default;
                }
                // Steps=新建列表<DebugStep>();
                return;
            }
            var pointBundleCount = BundleIndexing.GetBundleCount(points.Length);
            pool.Take<Vector3Wide>(pointBundleCount, out var pointBundles);
            // 虽然它通常不是渐近最优的,但礼品包装很简单,很容易进行高效的矢量化。
            // 作为第一步,创建输入数据的AOSOA版本。
            Vector3 centroid = default;
            for (int i = 0; i < points.Length; ++i)
            {
                BundleIndexing.GetBundleIndices(i, out var bundleIndex, out var innerIndex);
                ref var p = ref points[i];
                Vector3Wide.WriteSlot(p, innerIndex, ref pointBundles[bundleIndex]);
                centroid += p;
            }
            centroid /= points.Length;
            // 用质心填充最后几个位置。
            // 我们只假设最后一个部分包有几个额外的冗余内部点,从而避免了对它进行大量特殊情况的工作。
            var bundleSlots = pointBundles.Length * Vector<float>.Count;
            for (int i = points.Length; i < bundleSlots; ++i)
            {
                BundleIndexing.GetBundleIndices(i, out var bundleIndex, out var innerIndex);
                Vector3Wide.WriteSlot(centroid, innerIndex, ref pointBundles[bundleIndex]);
            }

            // 找一个起点。我们将使用离质心最远的那个。
            Vector3Wide.Broadcast(centroid, out var centroidBundle);
            Helpers.FillVectorWithLaneIndices(out var mostDistantIndicesBundle);
            var indexOffsetBundle = mostDistantIndicesBundle;
            Vector3Wide.DistanceSquared(pointBundles[0], centroidBundle, out var distanceSquaredBundle);
            for (int i = 1; i < pointBundles.Length; ++i)
            {
                var bundleIndices = new Vector<int>(i << BundleIndexing.VectorShift) + indexOffsetBundle;
                Vector3Wide.DistanceSquared(pointBundles[i], centroidBundle, out var distanceSquaredCandidate);
                mostDistantIndicesBundle = Vector.ConditionalSelect(Vector.GreaterThan(distanceSquaredCandidate, distanceSquaredBundle), bundleIndices, mostDistantIndicesBundle);
                distanceSquaredBundle = Vector.Max(distanceSquaredBundle, distanceSquaredCandidate);
            }
            var bestDistanceSquared = distanceSquaredBundle[0];
            var initialIndex = mostDistantIndicesBundle[0];
            for (int i = 1; i < Vector<int>.Count; ++i)
            {
                var distanceCandidate = distanceSquaredBundle[i];
                if (distanceCandidate > bestDistanceSquared)
                {
                    bestDistanceSquared = distanceCandidate;
                    initialIndex = mostDistantIndicesBundle[i];
                }
            }
            BundleIndexing.GetBundleIndices(initialIndex, out var mostDistantBundleIndex, out var mostDistantInnerIndex);
            Vector3Wide.ReadSlot(ref pointBundles[mostDistantBundleIndex], mostDistantInnerIndex, out var initialVertex);

            // 通过拾取要将所有顶点投影到其上的平面,然后测量该平面上的角度,可以找到所有其他点。
            // 我们选择测量的基本方向。对于第二个点,我们任意选择一个垂直方向。
            var initialToCentroid = centroid - initialVertex;
            var initialDistance = initialToCentroid.Length();
            if (initialDistance < 1e-7f)
            {
                // 点集没有任何体积或面积。
                pool.Take(1, out hullData.OriginalVertexMapping);
                hullData.OriginalVertexMapping[0] = 0;
                hullData.FaceStartIndices = default;
                hullData.FaceVertexIndices = default;
                // Steps=新建列表<DebugStep>();
                pool.Return(ref pointBundles);
                return;
            }
            Vector3Wide.Broadcast(initialToCentroid / initialDistance, out var initialBasisX);
            Helpers.FindPerpendicular(initialBasisX, out var initialBasisY); // (仅因为我们没有非捆绑版本,就在FindPervertical之前进行了广播)
            Vector3Wide.Broadcast(initialVertex, out var initialVertexBundle);
            pool.Take<Vector<float>>(pointBundles.Length, out var projectedOnX);
            pool.Take<Vector<float>>(pointBundles.Length, out var projectedOnY);
            var planeEpsilon = new Vector<float>((float)Math.Sqrt(bestDistanceSquared) * 1e-6f);
            var rawFaceVertexIndices = new QuickList<int>(pointBundles.Length * Vector<float>.Count, pool);
            var initialSourceEdge = new EdgeEndpoints { A = initialIndex, B = initialIndex };
            FindExtremeFace(initialBasisX, initialBasisY, initialVertexBundle, initialSourceEdge, ref pointBundles, indexOffsetBundle, points.Length,
               ref projectedOnX, ref projectedOnY, planeEpsilon, ref rawFaceVertexIndices, out var initialFaceNormal);
            Debug.Assert(rawFaceVertexIndices.Count >= 2);
            var facePoints = new QuickList<Vector2>(points.Length, pool);
            var reducedFaceIndices = new QuickList<int>(points.Length, pool);
            // 以后执行时会忽略发现不在面壳上的点。
            pool.Take<bool>(points.Length, out var allowVertex);
            for (int i = 0; i < points.Length; ++i)
                allowVertex[i] = true;

            Vector3Wide.ReadFirst(initialBasisX, out var debugInitialBasisX);
            Vector3Wide.ReadFirst(initialBasisY, out var debugInitialBasisY);
            // Steps=新建列表<DebugStep>();
            // var step=new DebugStep(initialSourceEdge,ref rawFaceVertexIndices,initialFaceNormal,debugInitialBasisX,debugInitialBasisY);

            ReduceFace(ref rawFaceVertexIndices, initialFaceNormal, ref points, ref facePoints, ref allowVertex, ref reducedFaceIndices);
            // step.AddReduced(ref ReducedFaceIndices,ref allowVertex);
            // steps.add(步骤);

            var earlyFaceIndices = new QuickList<int>(points.Length, pool);
            var earlyFaceStartIndices = new QuickList<int>(points.Length, pool);

            var edgesToTest = new QuickList<EdgeToTest>(points.Length, pool);
            var edgeFaceCounts = new QuickDictionary<EdgeEndpoints, int, EdgeEndpoints>(points.Length, pool);
            if (reducedFaceIndices.Count >= 3)
            {
                // 最初的脸部搜索发现了一个真实的脸部！这有点令人惊讶,因为我们不是从边缘偏移开始的,而是从任意方向开始的。
                // 不管怎样都要处理好。
                for (int i = 0; i < reducedFaceIndices.Count; ++i)
                {
                    ref var edgeToAdd = ref edgesToTest.Allocate(pool);
                    edgeToAdd.Endpoints.A = reducedFaceIndices[i == 0 ? reducedFaceIndices.Count - 1 : i - 1];
                    edgeToAdd.Endpoints.B = reducedFaceIndices[i];
                    edgeToAdd.FaceNormal = initialFaceNormal;
                    edgeToAdd.FaceIndex = 0;
                    edgeFaceCounts.AddRef(ref edgeToAdd.Endpoints, 1, pool);
                }
                // 因为找到了实际的面,所以我们继续并将其输出到面集。
                earlyFaceStartIndices.Allocate(pool) = earlyFaceIndices.Count;
                earlyFaceIndices.AddRange(reducedFaceIndices.Span, 0, reducedFaceIndices.Count, pool);
            }
            else
            {
                Debug.Assert(reducedFaceIndices.Count == 2,
                    "The point set size was verified to be at least 4 earlier, so even in degenerate cases, a second point should be found by the face search.");
                // 没有找到真正的脸。这是意料之中的;我们用来作为基础的任意方向很可能不会与任何边对齐。
                ref var edgeToAdd = ref edgesToTest.Allocate(pool);
                edgeToAdd.Endpoints.A = reducedFaceIndices[0];
                edgeToAdd.Endpoints.B = reducedFaceIndices[1];
                edgeToAdd.FaceNormal = initialFaceNormal;
                edgeToAdd.FaceIndex = -1;
                var edgeOffset = points[edgeToAdd.Endpoints.B] - points[edgeToAdd.Endpoints.A];
                var basisY = Vector3.Cross(edgeOffset, edgeToAdd.FaceNormal);
                var basisX = Vector3.Cross(edgeOffset, basisY);
                if (Vector3.Dot(basisX, edgeToAdd.FaceNormal) > 0)
                    Helpers.Swap(ref edgeToAdd.Endpoints.A, ref edgeToAdd.Endpoints.B);
            }

            while (edgesToTest.Count > 0)
            {
                edgesToTest.Pop(out var edgeToTest);
                // 确保新边尚未被另一个遍历填充。
                var faceCountIndex = edgeFaceCounts.IndexOf(edgeToTest.Endpoints);
                if (faceCountIndex >= 0 && edgeFaceCounts.Values[faceCountIndex] >= 2)
                    continue;

                ref var edgeA = ref points[edgeToTest.Endpoints.A];
                ref var edgeB = ref points[edgeToTest.Endpoints.B];
                var edgeOffset = edgeB - edgeA;
                // 面法线指向外部,边缘应逆时针缠绕。
                // basisY应指向远离源面的方向。
                var basisY = Vector3.Cross(edgeOffset, edgeToTest.FaceNormal);
                // basisX应该指向内部。
                var basisX = Vector3.Cross(edgeOffset, basisY);
                basisX = Vector3.Normalize(basisX);
                basisY = Vector3.Normalize(basisY);
                Vector3Wide.Broadcast(basisX, out var basisXBundle);
                Vector3Wide.Broadcast(basisY, out var basisYBundle);
                Vector3Wide.Broadcast(edgeA, out var basisOrigin);
                rawFaceVertexIndices.Count = 0;
                FindExtremeFace(basisXBundle, basisYBundle, basisOrigin, edgeToTest.Endpoints, ref pointBundles, indexOffsetBundle, points.Length, ref projectedOnX, ref projectedOnY, planeEpsilon, ref rawFaceVertexIndices, out var faceNormal);
                // step=new DebugStep(edgeToTest.Endpoint,ref rawFaceVertexIndices,faceNormal,basisX,basisY);
                reducedFaceIndices.Count = 0;
                facePoints.Count = 0;
                ReduceFace(ref rawFaceVertexIndices, faceNormal, ref points, ref facePoints, ref allowVertex, ref reducedFaceIndices);
                if (reducedFaceIndices.Count < 3)
                {
                    // 发现退化的面孔;不必费心为其创建工作。
                    continue;
                }
                // step.AddReduced(ref ReducedFaceIndices,ref allowVertex);
                // steps.add(步骤);

                var newFaceIndex = earlyFaceStartIndices.Count;
                earlyFaceStartIndices.Allocate(pool) = earlyFaceIndices.Count;
                earlyFaceIndices.AddRange(reducedFaceIndices.Span, 0, reducedFaceIndices.Count, pool);

                edgeFaceCounts.EnsureCapacity(edgeFaceCounts.Count + reducedFaceIndices.Count, pool);
                for (int i = 0; i < reducedFaceIndices.Count; ++i)
                {
                    EdgeToTest nextEdgeToTest;
                    nextEdgeToTest.Endpoints.A = reducedFaceIndices[i == 0 ? reducedFaceIndices.Count - 1 : i - 1];
                    nextEdgeToTest.Endpoints.B = reducedFaceIndices[i];
                    nextEdgeToTest.FaceNormal = faceNormal;
                    nextEdgeToTest.FaceIndex = newFaceIndex;
                    if (edgeFaceCounts.GetTableIndices(ref nextEdgeToTest.Endpoints, out var tableIndex, out var elementIndex))
                    {
                        ref var edgeFaceCount = ref edgeFaceCounts.Values[elementIndex];
                        // Debug.Assert(edgeFaceCount==1,
                        // "虽然我们允许继续执行,但这是一个错误情况,意味着正在生成重叠的三角形。"+
                        // "当有许多近乎共面的顶点时,这种情况往往会发生,因此不同面上的数值公差不能一致一致。");
                        ++edgeFaceCount;
                    }
                    else
                    {
                        // 这条边还没有被任何边认领。认领它作为新面,并添加边缘以进行进一步测试。
                        edgeFaceCounts.Keys[edgeFaceCounts.Count] = nextEdgeToTest.Endpoints;
                        edgeFaceCounts.Values[edgeFaceCounts.Count] = 1;
                        // 使用编码-所有索引都偏移1,因为0表示"空"。
                        edgeFaceCounts.Table[tableIndex] = ++edgeFaceCounts.Count;
                        edgesToTest.Allocate(pool) = nextEdgeToTest;
                    }
                }
            }

            edgesToTest.Dispose(pool);
            edgeFaceCounts.Dispose(pool);
            facePoints.Dispose(pool);
            reducedFaceIndices.Dispose(pool);
            rawFaceVertexIndices.Dispose(pool);
            pool.Return(ref allowVertex);
            pool.Return(ref projectedOnX);
            pool.Return(ref projectedOnY);
            pool.Return(ref pointBundles);

            // 从面顶点参照创建简化的外壳点集。
            pool.Take(earlyFaceStartIndices.Count, out hullData.FaceStartIndices);
            pool.Take(earlyFaceIndices.Count, out hullData.FaceVertexIndices);
            earlyFaceStartIndices.Span.CopyTo(0, hullData.FaceStartIndices, 0, earlyFaceStartIndices.Count);
            pool.Take<int>(points.Length, out var originalToHullIndexMapping);
            var hullToOriginalIndexMapping = new QuickList<int>(points.Length, pool);
            for (int i = 0; i < points.Length; ++i)
            {
                originalToHullIndexMapping[i] = -1;
            }
            for (int i = 0; i < earlyFaceStartIndices.Count; ++i)
            {
                var start = earlyFaceStartIndices[i];
                var nextIndex = i + 1;
                var end = earlyFaceStartIndices.Count == nextIndex ? earlyFaceIndices.Count : earlyFaceStartIndices[nextIndex];
                for (int j = start; j < end; ++j)
                {
                    var originalVertexIndex = earlyFaceIndices[j];
                    ref var originalToHull = ref originalToHullIndexMapping[originalVertexIndex];
                    if (originalToHull < 0)
                    {
                        // 这个顶点还没有被看到。
                        originalToHull = hullToOriginalIndexMapping.Count;
                        hullToOriginalIndexMapping.AllocateUnsafely() = originalVertexIndex;
                    }
                    hullData.FaceVertexIndices[j] = originalToHull;
                }
            }

            pool.Take(hullToOriginalIndexMapping.Count, out hullData.OriginalVertexMapping);
            hullToOriginalIndexMapping.Span.CopyTo(0, hullData.OriginalVertexMapping, 0, hullToOriginalIndexMapping.Count);

            pool.Return(ref originalToHullIndexMapping);
            hullToOriginalIndexMapping.Dispose(pool);
            earlyFaceIndices.Dispose(pool);
            earlyFaceStartIndices.Dispose(pool);
        }

        /// <summary>
        /// 将外壳线数据处理为运行时可用的凸面外壳线形状。使凸面外壳的点围绕其质心重新居中。
        /// </summary>
        /// <param name="Points">外壳数据索引到的点数组。</param>
        /// <param name="hullData">要处理的原始输入数据。</param>
        /// <param name="pool">用于为hullShape分配资源的池。</param>
        /// <param name="hullShape">从输入数据创建的凸面外壳形状。</param>
        /// <param name="center">在凸壳的点重新定心到原点之前计算其质心。</param>
        public static void CreateShape(Span<Vector3> points, HullData hullData, BufferPool pool, out Vector3 center, out ConvexHull hullShape)
        {
            hullShape = default;
            if (hullData.OriginalVertexMapping.Length < 3)
            {
                center = default;
                if (hullData.OriginalVertexMapping.Length > 0)
                {
                    for (int i = 0; i < hullData.OriginalVertexMapping.Length; ++i)
                    {
                        center += points[hullData.OriginalVertexMapping[i]];
                    }
                    center /= hullData.OriginalVertexMapping.Length;
                }
                return;
            }
            var pointBundleCount = BundleIndexing.GetBundleCount(hullData.OriginalVertexMapping.Length);
            pool.Take(pointBundleCount, out hullShape.Points);

            float volume = 0;
            center = default;
            for (int faceIndex = 0; faceIndex < hullData.FaceStartIndices.Length; ++faceIndex)
            {
                hullData.GetFace(faceIndex, out var face);
                for (int subtriangleIndex = 2; subtriangleIndex < face.VertexCount; ++subtriangleIndex)
                {
                    var a = points[face[0]];
                    var b = points[face[subtriangleIndex - 1]];
                    var c = points[face[subtriangleIndex]];
                    var volumeContribution = MeshInertiaHelper.ComputeTetrahedronVolume(a, b, c);
                    volume += volumeContribution;
                    center += (a + b + c) * volumeContribution;
                }
            }
            // 除以4,因为我们累加了(a+b+c),而不是实际的四面体中心(a+b+c+0)/4。
            center /= volume * 4;

            var lastIndex = hullData.OriginalVertexMapping.Length - 1;
            for (int bundleIndex = 0; bundleIndex < hullShape.Points.Length; ++bundleIndex)
            {
                ref var bundle = ref hullShape.Points[bundleIndex];
                for (int innerIndex = 0; innerIndex < Vector<float>.Count; ++innerIndex)
                {
                    var index = (bundleIndex << BundleIndexing.VectorShift) + innerIndex;
                    // 我们复制外壳中的最后一个顶点。这对性能没有影响;顶点包要么全部执行,要么不执行。
                    if (index > lastIndex)
                        index = lastIndex;
                    ref var point = ref points[hullData.OriginalVertexMapping[index]];
                    Vector3Wide.WriteSlot(point - center, innerIndex, ref bundle);
                }
            }

            // 创建面->顶点贴图。
            pool.Take(hullData.FaceStartIndices.Length, out hullShape.FaceToVertexIndicesStart);
            hullData.FaceStartIndices.CopyTo(0, hullShape.FaceToVertexIndicesStart, 0, hullShape.FaceToVertexIndicesStart.Length);
            pool.Take(hullData.FaceVertexIndices.Length, out hullShape.FaceVertexIndices);
            for (int i = 0; i < hullShape.FaceVertexIndices.Length; ++i)
            {
                BundleIndexing.GetBundleIndices(hullData.FaceVertexIndices[i], out var bundleIndex, out var innerIndex);
                ref var faceVertex = ref hullShape.FaceVertexIndices[i];
                faceVertex.BundleIndex = (ushort)bundleIndex;
                faceVertex.InnerIndex = (ushort)innerIndex;
            }

            // 创建边界平面。
            var faceBundleCount = BundleIndexing.GetBundleCount(hullShape.FaceToVertexIndicesStart.Length);
            pool.Take(faceBundleCount, out hullShape.BoundingPlanes);
            for (int i = 0; i < hullShape.FaceToVertexIndicesStart.Length; ++i)
            {
                hullShape.GetVertexIndicesForFace(i, out var faceVertexIndices);
                Debug.Assert(faceVertexIndices.Length >= 3, "We only allow the creation of convex hulls around point sets with, at minimum, some area, so all faces should have at least 3 points.");
                // 请注意,我们汇总了所有组成三角形的贡献。
                // 这避免了击中任何退化的面三角形,并平滑了较小的数值偏差。
                // (这在数学上等同于按面积加权平均,因为叉积的大小与面积成正比。)
                Vector3 faceNormal = default;
                hullShape.GetPoint(faceVertexIndices[0], out var facePivot);
                hullShape.GetPoint(faceVertexIndices[1], out var faceVertex);
                var previousOffset = faceVertex - facePivot;
                for (int j = 2; j < faceVertexIndices.Length; ++j)
                {
                    // 法线指向外部。
                    hullShape.GetPoint(faceVertexIndices[j], out faceVertex);
                    var offset = faceVertex - facePivot;
                    faceNormal += Vector3.Cross(previousOffset, offset);
                    previousOffset = offset;
                }
                var length = faceNormal.Length();
                Debug.Assert(length > 1e-10f, "Convex hull procedure should not output degenerate faces.");
                faceNormal /= length;
                BundleIndexing.GetBundleIndices(i, out var boundingPlaneBundleIndex, out var boundingPlaneInnerIndex);
                ref var boundingBundle = ref hullShape.BoundingPlanes[boundingPlaneBundleIndex];
                ref var boundingOffsetBundle = ref GatherScatter.GetOffsetInstance(ref boundingBundle, boundingPlaneInnerIndex);
                Vector3Wide.WriteFirst(faceNormal, ref boundingOffsetBundle.Normal);
                GatherScatter.GetFirst(ref boundingOffsetBundle.Offset) = Vector3.Dot(facePivot, faceNormal);
            }

            // 清除任何尾部边界平面数据以防止其贡献。
            var boundingPlaneCapacity = hullShape.BoundingPlanes.Length * Vector<float>.Count;
            for (int i = hullShape.FaceToVertexIndicesStart.Length; i < boundingPlaneCapacity; ++i)
            {
                BundleIndexing.GetBundleIndices(i, out var bundleIndex, out var innerIndex);
                ref var offsetInstance = ref GatherScatter.GetOffsetInstance(ref hullShape.BoundingPlanes[bundleIndex], innerIndex);
                Vector3Wide.WriteFirst(default, ref offsetInstance.Normal);
                GatherScatter.GetFirst(ref offsetInstance.Offset) = float.MinValue;
            }
        }

        /// <summary>
        /// 从输入点集中创建凸面外壳线形状。使凸面外壳的点围绕其质心重新居中。
        /// </summary>
        /// <param name="Points">用于创建船体的点。</param>
        /// <param name="pool">用于临时分配和输出数据结构的缓冲池。</param>
        /// <param name="hullData">处理到凸包中的中间包数据。</param>
        /// <param name="center">在凸壳的点重新定心到原点之前计算其质心。</param>
        /// <param name="venexHull">输入点集的凸包形状。</param>
        public static void CreateShape(Span<Vector3> points, BufferPool pool, out HullData hullData, out Vector3 center, out ConvexHull convexHull)
        {
            ComputeHull(points, pool, out hullData);
            CreateShape(points, hullData, pool, out center, out convexHull);
        }

        /// <summary>
        /// 从输入点集中创建凸面外壳线形状。使凸面外壳的点围绕其质心重新居中。
        /// </summary>
        /// <param name="Points">用于创建船体的点。</param>
        /// <param name="pool">用于临时分配和输出数据结构的缓冲池。</param>
        /// <param name="center">在凸壳的点重新定心到原点之前计算其质心。</param>
        /// <param name="venexHull">输入点集的凸包形状。</param>
        public static void CreateShape(Span<Vector3> points, BufferPool pool, out Vector3 center, out ConvexHull convexHull)
        {
            ComputeHull(points, pool, out var hullData);
            CreateShape(points, hullData, pool, out center, out convexHull);
            // 空的输入点集不会分配。
            if (hullData.OriginalVertexMapping.Allocated)
                hullData.Dispose(pool);
        }
    }
}
